package com.leetcode;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No20
 * @description https://leetcode-cn.com/problems/valid-parentheses/
 * @date 2021/2/5 下午2:56
 */
public class No20 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        boolean res = isValid(s);
        System.out.println(res);

    }

    public static boolean isValid(String s) {
        if(s == null || s.length() < 1){
            return false;
        }
        int len = s.length();
        char[] str = s.toCharArray();
        LinkedList<Character> stack = new LinkedList<>();
        for(char c:str){
            if(c == '(' || c == '{' || c == '['){
                stack.addLast(c);
            }
            if(c == ')'){
                if(stack.isEmpty() || stack.getLast() != '('){
                    return false;
                }
                if(stack.getLast() == '('){
                    stack.removeLast();
                }
            }
            if(c == ']'){
                if(stack.isEmpty() || stack.getLast() != '['){
                    return false;
                }
                if(stack.getLast() == '['){
                    stack.removeLast();
                }
            }
            if(c == '}'){
                if(stack.isEmpty() || stack.getLast() != '{'){
                    return false;
                }
                if(stack.getLast() == '{'){
                    stack.removeLast();
                }
            }
        }
        return stack.isEmpty();
    }

}
